import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author:gao
 * @date:2020/6/11
 * @time:11:12
 * @version:0.0.1
 * @description:none
 */


//739.每日温度

//单调栈，好妙啊
//class Solution{
//    public int[] dailyTemperatures(int[] T){
//        Stack<Integer> stack = new Stack<>();
//        int len = T.length;
//        int[] ans = new int[len];
//        for (int i=0;i<len;i++){
//            while ((!stack.empty()&&T[i]>T[stack.peek()])){
//                ans[stack.peek()]=i-stack.peek();
//                stack.pop();
//            }
//            stack.push(i);
//        }
//        return ans;
//    }
//}
//
////自己的解法，时间O（n）,但是效率不如官方单调栈解法
//class Solution_five {
//    public int[] dailyTemperatures(int[] T) {
//        int len = T.length;
//        int[] ans = new int[len];
//        int[] tmp = new int[101];
//        ans[len-1] =0;
//        tmp[T[len-1]]=len-1;
//        //通过从后往前标记辅助数组，表示本数据已经有了，
//        //然后从比本次遍历的数组元素大的辅助数组开始遍历，
//        //直至找到数值大于当前且下表差最小的
//        for(int i= len-2;i>=0;i--){
//            int n = T[i];
//            tmp[n] = i;
//            boolean su =false;
//            int ans_tmp =Integer.MAX_VALUE;
//            for(int j= n+1;j<=100;j++){
//                if(tmp[j]>i){
//                    ans_tmp = Integer.min(ans_tmp,tmp[j]-i);
//                    su =true;
//                }
//                if(su){
//                    ans[i] = ans_tmp;
//                }
//            }
//            if(!su){
//                ans[i]=0;
//            }
//        }
//        return ans;
//    }
//}
